#include <stdio.h>
//图的遍历之深度优先搜索 P196
#define MAXSIZE 100
typedef char ElemType;
//图的声明：邻接矩阵（一个顶点数组+一个边数组）
typedef struct 
{
    ElemType vertex[MAXSIZE]; //用数组存放顶点
    int edge[MAXSIZE][MAXSIZE];//用二维数组存放边
    int vertex_num; //顶点个数
    int edge_num; //边的个数
}mat_graph;
//图的创建：顶点+边
void creatgraph(mat_graph *g)
{
    g->vertex_num=9;
    g->edge_num=15;
    //顶点：按照深度优先遍历的顺序
    g->vertex[0]='A';
    g->vertex[1]='B';
    g->vertex[2]='C';
    g->vertex[3]='D';
    g->vertex[4]='E';
    g->vertex[5]='F';
    g->vertex[6]='G';
    g->vertex[7]='H';
    g->vertex[8]='I';
    //边：
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            g->edge[i][j]=0;
        }
    }
    //A-B A-F
    g->edge[0][1]=1;
    g->edge[0][5]=1;
    //B-C B-G B-I
    g->edge[1][2]=1;
    g->edge[1][6]=1;
    g->edge[1][8]=1;
    //C-D C-I
    g->edge[2][3]=1;
    g->edge[2][8]=1;
    //D-E D-G D-H D-I
    g->edge[3][4]=1;
    g->edge[3][6]=1;
    g->edge[3][7]=1;
    g->edge[3][8]=1;
    //E-F E-H
    g->edge[4][5]=1;
    g->edge[4][7]=1;
    //F-G
    g->edge[5][6]=1;
    //G-H
    g->edge[6][7]=1;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<i;j++)
        {
            g->edge[i][j]=g->edge[j][i];
        }
    }
}
//图的深度遍历：递归
int visited[MAXSIZE]={0};//存放顶点是否被访问的信息，下标与顶点数组一致
void dfs(mat_graph g,int i)
{
    visited[i]=1;
    printf("%c",g.vertex[i]);
    int j; //代表顶点在边数组中第j列，以此获得要遍历那个顶点与其他顶点存在的边关系
    for(j=0;j<g.vertex_num;j++)
    {
        if(g.edge[i][j]==1&&visited[j]==0)  
        {
            dfs(g,j);
        }
    } 
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    int i=0; //代表要遍历的那个顶点在边数组中第i行
    dfs(g,i);
    return 0;
}